Mines 2023 - La typographie informatisée

Partie I - Préambule

Q1

On convertit 100 en base 16 : $0*1+0*16*1*16^2 = 256$ ; cela fait 2.56$

Q2

v = [[[0.25,1.0],[0.25,-1.0],[0.0,-1.0]],[[0.25,1.25]]]

v[0]

[[0.25, 1.0], [0.25, -1.0], [0.0, -1.0]]

import matplotlib.pyplot as plt

plt.plot([0.25,0.25,0],[1,-1,-1])
plt.scatter([0.25],[1.25],1)  # pour faire le point tout seul sinon on ne le voit pas
plt.grid()
plt.axis('equal');

Partie II - Gestion de polices de caractères vectorielles

Q3

On veut compter le nombre de glyphe en Roman : on compte le nombre d'enregistrements dans la table Glyphe pour lesquels l'attribut groman est True :

SELECT COUNT(*)
FROM Glyphe
WHERE groman = True

Q4

On peut soit supposer qu'on connait le code du caractère 'A' (65) : on a besoin de la table Police pour récupérer le pid dont le pnom est Helvetica et de la table Glyphe pour récupérer le contenu de gdesc

SELECT desc 
FROM Glyphe
JOIN Police ON Glyphe.pid=Police.pid
WHERE
pnom = "Helvetica" AND code=65 AND Glyphe.Roman=False

Si on ne veut pas connaître le code du caractère 'A', il faut en plus le récupérer dans la table Caractere ce qui ajoute une jonction supplémentaire :

SELECT desc
FROM Glyphe 
JOIN Police ON Glyphe.pid=Police.pid
JOIN Caractere ON Caractere.code=Glyphe.code
WHERE
pnom = "Helvetica" AND car='A' AND Glyphe.Roman=False

Q5

On utilise les deux tables Famille et Police : on effectue un regroupement par paquets sur le fid de Famille, on ne conserve que celles qui ont un nombre de pid non nul, et on trie :

SELECT fnom, COUNT(pid) as nombre
FROM Famille
JOIN Police ON Police.fid=Famille.fid
GROUP BY fnom
HAVING nombre>0
ORDER BY fnom

Partie II - Manipulation de descriptions vectorielles de glyphes

Q6

def points(v):
    L = []              # liste des points
    for ml in v:        # on parcourt les multi-lignes
        for point in ml:
            L.append(point)
    return L        

points(v)

Q7

def dim(l,n):
    L = []
    for x in l:
        L.append(x[n])
    return L

l = [[1,2],[3,4],[5,6],[7,8]]
dim(l,1)

dim(l,0)

Q8

On récupère tous les points du glyphe, puis les premières coordonnées. On n'a plus qu'à prendre les extrema

def largeur(v):
    p = points(v)
    abscisses = dim(p,0)
    return max(abscisses)-min(abscisses)    

largeur(v)

Q9

def obtention_margeur(police):
    L = []
    debut = ord('a')
    for car in range(debut,debut+26):
        L.append(largeur(glyphe(chr(car),police,True)))
        L.append(largeur(glyphe(chr(car),police,False)))
    return L        

Q10

Comme indiqué, la fonction f s'applique aux points - on doit donc parcourir les différentes multi-lignes du glyphe et appliquer la fonction à chacun de ses points

def transforme(f,v):
    L = []
    for ml in v:
        nouvelle_ml = []
        for p in ml:
            nouvelle_ml.append(f(p))
        L.append(nouvelle_ml)
    return L

On peut aussi utiliser la construction de liste par compréhension (qui réalise la même chose que parcourir une liste et ajouter à la nouvelle liste)

def transforme(f,v):
    v2 = [[f(p) for p in ml] for ml in v]
    return v2

Q11

L'application zzz est l'application $(x,y)\mapsto (0.5*x,y)$. Les abscisses sont divisées par $2$, les ordonnées ne changent pas. On divise la largeur du glyphe par $2$

Q12

def penche(v):
    def f(p):
        x,y = p
        return [x+0.5*y,y]
    return transforme(f,v)

IV Rasterisation

from PIL import Image

im = Image.new("1", (50, 100), color=1)
for y in range(60, 65):
    for x in range(5, 45):
        im.putpixel((x, y), 0)
        im.putpixel((x, y-20), 0)
im.save("egal.png")
plt.imshow(im)

from math import floor

def trace_quadrant_est(im, p0, p1):
    x0, y0 = p0
    x1, y1 = p1
    dx, dy = x1-x0, y1-y0
    im.putpixel(p0, 0)
    for i in range(1, dx):
        p = (x0 + i, y0 + floor(0.5 + dy * i / dx))
        im.putpixel(p, 0)
    im.putpixel(p1, 0)
im = Image.new("1", (10, 10), color=1)
trace_quadrant_est(im, (0, 0), (6, 2))
trace_quadrant_est(im, (9, 8), (1, 9))
trace_quadrant_est(im, (3, 0), (5, 8))
plt.imshow(im);  # à la place du im.show() qui affiche ailleurs

Pour la ligne 15: on trace une ligne entre les points de coordonnées (0,0) et (6,2) :

• dx:=6 et dy:=2
• on trace le premier point de coordonnées (0,0)
• la boucle sur i va de 1 à 5 (compris) pour les 5 points intermédiaires, on obtient les points (1,0), (2,1), (3,1), (4,1), (5,2)
• on place le dernier point (6,2)

Q14

Cette fois on a dx=-8 donc aucun passage dans la boucle for ; on a les deux points extrêmes qui apparaissent (placés en dehors de la boucle) et c'est tout. Le problème provient donc qu'on doit reculer

Q15

On a dx=2 ; à part les 2 points aux extrémités, il n'y a qu'un passage dans la boucle et ainsi un seul point intermédiaire. La pente est trop grande (plus que $1$ en valeur absolue et on oublie des points)

Q16

def trace_quadrant_sud(im, p0, p1):
    x0, y0 = p0
    x1, y1 = p1
    dx, dy = x1-x0, y1-y0
    im.putpixel(p0, 0)
    for j in range(1, dy):
        p = (x0 + floor(0.5+dx*j / dy), y0 + j)
        im.putpixel(p, 0)
    im.putpixel(p1, 0)
im = Image.new("1", (10, 10), color=1)
trace_quadrant_sud(im, (3, 0), (5, 8))
plt.imshow(im);  # à la place du im.show() qui affiche ailleurs

Q17

def trace_segment(im,p0,p1):
    x0, y0 = p0
    x1, y1 = p1
    dx, dy = x1-x0, y1-y0
    if abs(dy)<abs(dx):      # |dy/dx|<1 - on est plus proche de l'horizontale
        if x0<x1:            # p0 est à droite de p1
            trace_quadrant_est(im,p0,p1)
        else:                # p1 est à droite de p0
            trace_quadrant_est(im,p1,p0)
    else:                    # plutôt vertical
        if y0<y1:
            trace_quadrant_sud(im,p0,p1)
        else:
            trace_quadrant_sud(im,p1,p0)

# on teste... tout est multiplié par 100 pour avoir une meilleure résolution
im = Image.new("1", (1000, 1000), color=1)
trace_segment(im, (0, 0), (600, 200))
trace_segment(im, (900, 800), (100, 900))
trace_segment(im, (300, 0), (500, 800))
trace_segment(im, (800,300), (100,600))
# test pour un point unique
trace_segment(im, (250,250),(250,250))
plt.imshow(im);

Partie V - Affichage du texte

Q18

from math import floor

def position(p,pz,taille):
    centre_x,centre_y = pz # coordonnées du point (0,0) dans le repère de l'écran/de l'image
    x,y = p # coordonnées normalisées
    pos_x = floor(centre_x + taille*x)
    pos_y = floor(centre_y - taille*y)
    return pos_x,pos_y
    

position((1,1),(100,100),1)

(101, 99)

Q19

def affiche_car(page, c, police,roman, pz, taille):
    v = glyphe(c, police, roman)                  # récupère la liste de listes de points
    for ml in v:                                  # on parcourt les multilignes
        point = ml[0]                             # point de départ
        cx,cy = position(point,pz,taille)         # point de départ dans le repère de l'image
        g,d = cx,cx                               # valeurs les plus à gauche et à droite
        trace_segment(page,[cx,cy],[cx,cy])       # on trace le premier point (au cas où il serait tout seul)
        for k in range(1,len(ml)):
            cx2,cy2 = position(ml[k],pz,taille)   # nouveau point
            g = min(g,cx2)
            d = min(d,cx2)
            trace_segment(page,[cx,cy],[cx2,cy2]) # segment entre l'ancien et le nouveau point
            cx,cy = cx2,cy2                       # le nouveau point devient le prochain départ 
    return d-g+1
    # return taille*largeur(v)
            

Q20

def affiche_mot(page, mot, ic, police, roman, pz, taille):
    x,y = pz 
    for c in mot:
        largeur = affiche_car(page, c, police, roman, [x,y], taille)
        x += largeur+ic  # nouvelle abscisse de départ
    return x-largeur-ic  # on recule de l'espace qu'on a ajouté

Partie VI - Justification d'un paragraphe

Q21

def glouton(Lmots:[int],L:int)->[[int]]:
    lignes=[]
    nligne=[]
    l=0
    for c in Lmots :
        if (c + l) > L:
            lignes.append(nligne)
            nligne=[c]
            l=c+1
        else:
            l=l+c+1
            nligne.append(c)
    lignes.append(nligne)
    return lignes

glouton([3,7,5,4,8,6,3,4,2,6,4,3,5],20)

[[3, 7, 5], [4, 8, 6], [3, 4, 2, 6], [4, 3, 5]]

Le principe :

• on ajoute des mots tant qu'on ne dépasse pas la taille de la ligne ; la variable l désigne le nombre de caractères dans la ligne actuelle
• si l'ajout fait déborder (ligne 6 : l+c > L) alors on ajoute la ligne actuelle à la liste des lignes, on repart d'une nouvelle ligne avec le mot en train d'être placé
• sinon on ajoute la taille du mot + 1 pour l'espace (ligne 11)

On dit que l'algorithme est glouton car il prend les mots les uns après les autres et le place sans regarder globalement s'il n'y aurait pas un meilleur équilibre (c'est une optimisation locale et pas globale)

# test sur l'exemple proposé
lmots = [2,4,2,6,6]
glouton(lmots,10)

[[2, 4, 2], [6], [6]]

def cout(i:int,j:int,lmots:[int],L:int)->int:
    res=sum(lmots[i:j+1])+(j-i)
    if res>L:
        return float("inf")
    else:
        return (L-res)**2

Q22

On regarde sur les deux situations :

• algorithme glouton :
  • les séparations sont i=0,j=2 puis i=j=3 et enfin i=j=4
  • les coûts sur chaque ligne : $(10-2-8)^2$, $(10-0-6)^2$ et $(10-0-6)^2$
  • ce qui donne un coût total de $32$
• seconde répartition :
  • les séparations sont i=0,j=1 puis i=2,j=3 et enfin i=j=4
  • les coûts sur chaque ligne : $(10-1-6)^2$, $(10-1-8)^2$ et $(10-0-6)^2$
  • ce qui donne un coût total de $26$

Q23

L'idée pour mémoïser est de stocker les valeurs de $d$ qu'on a déjà trouvées. Lorsqu'on a besoin de calculer une valeur de $d$, on regarde si on la connaît déjà (l'algorithme renvoie cette valeur) et sinon on la calcule. On stocke tout cela dans un dictionnaire memo :

memo = {len(lmots) : 0}

def progd_memo(i,lmots,L, memo):
    if i in memo:
        return memo[i]
    else:
        mini =float("inf")
        for j in range(i+1,len(lmots)+1):
            d = progd_memo(j,lmots,L,memo)+cout(i,j-1,lmots,L)
            if d<mini:
                mini = d
        memo[i] = mini
        return mini

progd_memo(0,lmots,10,memo)

26

memo

{5: 0, 4: 16, 3: 32, 2: 17, 1: 41, 0: 26}

Comment comprendre ces valeurs :

• 5:0 -> pas de mot à placer
• 4:16 -> le coût le plus faible pour placer à partir du mot 4 (il n'y en a plus qu'un) est de le placer seul (taille $6$, cout de $16$)
• 3:32 -> idem avec les mots 3 et 4 (chacun sur une ligne, cout $16+16=32$
• 2:17 -> mots 2,3 et 4 ; 2 lignes (2+' '+6 : cout $1$, et le dernier mot seul : coût $16$)
• 1:41 -> ...
• 0:26 -> on places les mots de 0 à 4 ; meilleur coût à $26$

Q24

La fonction cout(i,j) demande $1+1+1+(j-i+1)+1=j-i+5$ opérations d'additions ou multiplications (le dernier $+1$ est pour le carré sauf s'il n'y est pas)

Si on note $C(i,n)$ le coût pour calculer $d(i)$ par la formule récursive pour $n$ mots (c'est-à-dire qu'on refait le calcul des $d(j)$ suivants), on obtient une relation $$ C(i,n) = \displaystyle\sum_{j=i+1}^n \left(C(j)+f(i,j)\right)$$ où $f(i,j)$ est le nombre d'opérations dans le calcul de cout(i,j-1), donc au moins $j-i+4$

Si on note $D(n)$ la complexité pour le placement pour $n$ mots, on a une minoration très très large $D_{n+2}\geqslant D_{n+1}+D_n$ et donc une croissance exponentielle

Pour la version progd_bashaut : on a deux boucles imbriquées (avec au plus $n$ étapes chacunes), à l'intérieur la complexité principale est le calcul de la fonction cout (+1 addition), donc en $O(n)$. Finalement l'algorithme est de complexité $O(n^3)$.

def progd_bashaut(lmots:[int],L:int,t:[int])->int:
    M=[0]*(len(lmots)+1)
    for i in range(len(lmots)-1,-1,-1):
        mini,indi=float("inf"),-1
        for j in range(i+1,len(lmots)+1):
            d=M[j]+cout(i,j-1,lmots,L)
            if d<mini:
                mini,indi=d,j
        t[i]=indi
        M[i]=mini
    return M[-1]

t = [0]*(len(lmots))
progd_bashaut(lmots,10,t)
t

[2, 3, 4, 4, 5]

Q25

def lignes(mots,t,L):
    Liste = []
    n = len(mots)
    depart = 0                    # numéro du mot actuel (début d'une ligne)
    while depart<n:
        fin = t[depart]           # c'est le niveau où on doit couper
        s_L = mots[depart:fin]    # on crée la liste des mots entre ces deux positions (la seconde est exclu, ça commence la ligne suivante)
        Liste.append(s_L)         # on ajoute cette liste à la liste des mots d'une ligne
        depart = fin              # numéro du mot pour la ligne suivante
    return Liste

t=[2, 3, 5, 5, 5, 6, 7, 9, 11, 11, 11]
L=15
mots=["Lorem","ipsum","dolor","sit","amet,","consectetur","adipiscing",
"elit.","Sed","non","risus."]

A = lignes(mots,t,L) ; A

[['Lorem', 'ipsum'],
 ['dolor', 'sit', 'amet,'],
 ['consectetur'],
 ['adipiscing'],
 ['elit.', 'Sed'],
 ['non', 'risus.']]

Q26

def formatage(lignedemots,L):
    texte_formaté = ""
    for ligne in lignedemots:
        longueur = 0
        ligne_actuelle = ""
        for m in ligne:
            longueur += len(m)
        n_mots = len(ligne)
        cases = n_mots-1       # nombre de trous à remplir
        restant = L-longueur   # nombre d'espaces à placer
        if len(ligne)==1:
            ligne_actuelle = ligne[0]+restant*' '
        else:
            deja_fait = 0
            ligne_actuelle = ligne[0]
            for j in range(1,n_mots):
                espaces_depuis_debut = j*restant//cases
                nouveaux_espaces = espaces_depuis_debut-deja_fait
                ligne_actuelle += " "*(nouveaux_espaces)+ligne[j]
                deja_fait = espaces_depuis_debut
        texte_formaté += ligne_actuelle+"\n"
    return texte_formaté

print(formatage(A,15))

Lorem     ipsum
dolor sit amet,
consectetur    
adipiscing     
elit.       Sed
non      risus.